11866 요세푸스 문제 0
TLDR
- 큐 만들기
- K-1번 큐에서 POP, PUSH를 한다.
- 큐에서 한 명을 POP한다. 그 결과를 요세푸스 순열 뒤에 붙인다.
- 2번으로 돌아가 한 사람이 남을 때까지 반복한다.
- 마지막 남은 한 사람을 요세푸스 순열 뒤에 추가한다.
Snippet
"""
http://boj.kr/11866
- Memory: 34916KB
- Time: 68
"""
from collections.abc import Generator
from collections import deque
def main(n, k) -> Generator[int, None, None]:
"""
N 명의 사람이 원형으로 앉아있고 매번 K 번째 사람을 제거하였을 때
사람이 제거된 순서를 (N,K) 요세푸스 순열이라고 한다.
이 요세푸스 순열을 반환하라.
"""
# 1. 큐 만들기
q = deque(range(1, n + 1))
# 4. 한 사람이 남을 때까지 반복한다.
while len(q) > 1:
# 2. K-1번 큐에서 POP & PUSH 한다. 이 사람들은 자신의 차례가 아니다.
for _ in range(k - 1):
popped = q.popleft()
q.append(popped)
# 3. 큐에서 한 명을 POP하고 그 결과를 요세푸스 순열의 뒤에 추가한다.
yield q.popleft()
# 5. 마지막 남은 한 사람을 요세푸스 순열의 뒤에 추가한다.
yield q[0]
if __name__ == "__main__":
n, k = map(int, input().split())
print(f"<{', '.join(map(str, main(n, k)))}>")
두 명을 남기면 조금 더 빠르게 프로그램이 끝나지 않을까? 별 차이는 없었다.
"""
http://boj.kr/11866
- Memory: 34900
- Time: 68ms
"""
from collections.abc import Generator
from collections import deque
def main(n, k) -> Generator[int, None, None]:
"""
N 명의 사람이 원형으로 앉아있고 매번 K 번째 사람을 제거하였을 때
사람이 제거된 순서를 (N,K) 요세푸스 순열이라고 한다.
이 요세푸스 순열을 반환하라.
"""
if n == 1:
yield 1
return
# 1. 큐 만들기
q = deque(range(1, n + 1))
# 4. 두 사람이 남을 때까지 반복한다.
while len(q) > 2:
# 2. K-1번 큐에서 POP & PUSH 한다. 이 사람들은 자신의 차례가 아니다.
for _ in range(k - 1):
popped = q.popleft()
q.append(popped)
# 3. 큐에서 한 명을 POP하고 그 결과를 요세푸스 순열의 뒤에 추가한다.
yield q.popleft()
# 5. 마지막 남은 두 사람을 요세푸스 순열의 뒤에 추가한다.
last1, last2 = q[0], q[1]
if k % 2 == 0:
last1, last2 = last2, last1
yield last1
yield last2
if __name__ == "__main__":
n, k = map(int, input().split())
print(f"<{', '.join(map(str, main(n, k)))}>")
Sample Input & Expected Output
Input
Expected Output